Maximal antichains of minimum size

Title: Maximal antichains of minimum size
Creator: Kalinowski, Thomas; Leck, Uwe; Roberts, Ian T.
Relation: Electronic Journal of Combinatorics Vol. 20, Issue 2, p. 1-14
Relation: http://www.combinatorics.org/ojs/index.php/eljc/issue/view/Volume20-2
Publisher: Electronic Journal of Combinatorics
Resource Type: journal article
Date: 2013
Description: Let n ⩾4 be a natural number, and let K be a set K⊆[n]:={1,2,...,n}. We study the problem of finding the smallest possible size of a maximal family A of subsets of [n] such that A contains only sets whose size is in K, and A⊈B for all {A,B}⊆A, i.e. A is an antichain. We present a general construction of such antichains for sets K containing 2, but not 1. If 3∈K our construction asymptotically yields the smallest possible size of such a family, up to an o(n²) error. We conjecture our construction to be asymptotically optimal also for 3∉K, and we prove a weaker bound for the case K={2,4}. Our asymptotic results are straightforward applications of the graph removal lemma to an equivalent reformulation of the problem in extremal graph theory, which is interesting in its own right.
Subject: extremal set theory; Sperner property; maximal antichains; flat antichains
Identifier: http://hdl.handle.net/1959.13/1295427
Identifier: uon:19022
Identifier: ISSN:1077-8926
Language: eng
Full Text
Reviewed

		Thumbnail	File	Description	Size	Format
View Details Download			ATTACHMENT02	Publisher version (open access)	289 KB	Adobe Acrobat PDF	View Details Download